package 力扣面试经典150;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-05
 * Time:16:30
 */

/**
 * 力扣面试经典150:68. 文本左右对齐
 * 困难
 * 相关标签
 * 相关企业
 * 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
 * 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 * 注意:
 *     单词是指由非空格字符组成的字符序列。
 *     每个单词的长度大于 0，小于等于 maxWidth。
 *     输入单词数组 words 至少包含一个单词。
 * 示例 1:
 * 输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
 * 输出:
 * [
 *    "This    is    an",
 *    "example  of text",
 *    "justification.  "
 * ]
 */
public class fullJustify {
    public static void main(String[] args) {
        String[] words = {"What","must","be","acknowledgment","shall","be"};
        int maxWidth = 16;

        List<String> result = fullJustify(words, maxWidth);

        // 输出处理后的文本行
        for (String line : result) {
            System.out.println(line);
        }
    }
//    public static List<String> fullJustify(String[] words, int maxWidth) {
//        List<String> list = new ArrayList<>();
//        StringBuffer str = new StringBuffer();
//        int index = 0;
//        while(index < words.length){
//            if((str.length() + words[index].length()) <= maxWidth){
//                str.append(words[index]);
//                str.append(" ");
//            }else{
//                if(str.charAt(str.length() - 1) == ' '){
//                    //为保持对齐需要插入的空格数
//                    int c = ((maxWidth - str.length()) + 1) / (index - 1);
//                    if (c != 0){
//                        for (int i = 0; i < str.length(); i++) {
//                            if (str.charAt(i) == ' '){
//                                for (int j = 0; j < c; j++) {
//                                    str.insert(i,' ');
//                                }
//                                i += c;
//                            }
//                        }
//                    }else {
//                        int n = maxWidth - str.length() + 1;
//                        for (int i = 0; i < str.length(); i++) {
//                            if (str.charAt(i) == ' '){
//                                for (int j = 0; j < n; j++) {
//                                    str.insert(i,' ');
//                                }
//                                n -= n;
//                                i += c;
//                            }
//                        }
//                    }
//                    String s = str.substring(0,str.length() - 1 - c);
//                    str = new StringBuffer();
//                    list.add(s);
//                }
//                index--;
//            }
//            index++;
//        }
//        index--;
//        if(str.charAt(str.length() - 1) == ' '){
//            //为保持对齐需要插入的空格数
//            int c = ((maxWidth - str.length()) + 1) / (index - 1);
//            if (c != 0){
//                for (int i = 0; i < str.length(); i++) {
//                    if (str.charAt(i) == ' '){
//                        for (int j = 0; j < c; j++) {
//                            str.insert(i,' ');
//                        }
//                        i += c;
//                    }
//                }
//            }else {
//                int n = maxWidth - str.length() + 1;
//                for (int i = 0; i < str.length(); i++) {
//                    if (str.charAt(i) == ' '){
//                        for (int j = 0; j < n; j++) {
//                            str.insert(i,' ');
//                        }
//                        n -= n;
//                        i += c;
//                    }
//                }
//            }
//            String s = str.substring(0,str.length() - 1 - c);
//            list.add(s);
//        }
//        return list;
//    }
    public static List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        int index = 0;

        while (index < words.length) {
            int start = index;
            int end = index;
            int totalLength = words[index].length();

            // 找出当前行能容纳的单词范围
            while (end + 1 < words.length && totalLength + words[end + 1].length() + 1 <= maxWidth) {
                end++;
                totalLength += words[end].length() + 1;
            }

            StringBuilder line = new StringBuilder();

            // 构建当前行
            if (start == end || end == words.length - 1) { // 单词只有一个或为最后一行，左对齐
                for (int i = start; i <= end; i++) {
                    line.append(words[i]);
                    if (i < end) {
                        line.append(" ");
                    }
                }
                while (line.length() < maxWidth) {
                    line.append(" ");
                }
            } else { // 其他行，完全对齐
                int spaces = maxWidth - totalLength + (end - start);
                int spaceSlots = end - start;
                int spacePerSlot = spaces / spaceSlots;
                int extraSpaces = spaces % spaceSlots;

                for (int i = start; i <= end; i++) {
                    line.append(words[i]);
                    if (i < end) {
                        for (int j = 0; j < spacePerSlot; j++) {
                            line.append(" ");
                        }
                        if (extraSpaces > 0) {
                            line.append(" ");
                            extraSpaces--;
                        }
                    }
                }
            }

            result.add(line.toString());
            index = end + 1;
        }

        return result;
    }


}
